package Recursion;

import java.util.Arrays;

public class RecursionProblem {

    //青蛙跳楼梯
    public static void main(String[] args) {
        System.out.println(jumpStairs(4));

    }
    public static int jumpStairs (int n ) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return jumpStairs(n - 1) + jumpStairs(n - 2);
    }

    //用递归实现斐波那契
    public static void main4(String[] args) {
        System.out.println(fibonacci(3));
        System.out.println(fibonacci(4));
        System.out.println(fibonacci(5));
        System.out.println(fibonacci(6));
        System.out.println(fibonacci(7));
        System.out.println(fibonacci(8));
    }

    //0 1 2 3 4 5
    //1 1 2 3 5 8
    public static int fibonacci (int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        if (n == 0) {
            return 0;
        }
        return fibonacci(n - 2) + fibonacci(n-1);
    }

    //递归实现插入排序
    public static void main3(String[] args) {
        int[] arr = {1,3,5,3,8,9,11};

        insert(arr,1);
        System.out.println(Arrays.toString(arr));
    }

    public static void insert (int[] arr, int low) {
        if (low == arr.length) {
            return;
        }
        int temp = arr[low];
        int i = low - 1;

        while (i >= 0 && arr[i] > temp) {
            arr[i + 1] = arr[i];
            i--;
        }
        arr[i + 1] = temp;

        insert(arr,low + 1);
    }

    //用递归实现冒泡2.0
    public static void main2(String[] args) {
        int[] arr = {1,5,3,2,4,6,10};
        bubble(arr,arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }
    public static void bubble(int[] arr,int num) {

        if (num == 0) {
            return;
        }
        int x = 0;
        for (int i = 0; i < num; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
                x = i;
            }
        }
        bubble(arr,x);
    }

    //用递归实现冒泡
/*    public static void main1(String[] args) {
        int[] arr = {1,5,3,2,4,6,1};
        bubble(arr,arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }
    public static void bubble(int[] arr,int num) {

        if (num == 0) {
            return;
        }
        for (int i = 0; i < num; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
        bubble(arr,num-1);
    }*/
}
